<!DOCTYPE HTML>
<html lang="zh-Hans" class="sidebar-visible no-js light">
    <head>
        <!-- Book generated using mdBook -->
        <meta charset="UTF-8">
        <title>700行Rust写一个内存分配器 - Rust 优秀博文</title>


        <!-- Custom HTML head -->
        
        <meta content="text/html; charset=utf-8" http-equiv="Content-Type">
        <meta name="description" content="">
        <meta name="viewport" content="width=device-width, initial-scale=1">
        <meta name="theme-color" content="#ffffff" />

        <link rel="icon" href="../../favicon.svg">
        <link rel="shortcut icon" href="../../favicon.png">
        <link rel="stylesheet" href="../../css/variables.css">
        <link rel="stylesheet" href="../../css/general.css">
        <link rel="stylesheet" href="../../css/chrome.css">
        <link rel="stylesheet" href="../../css/print.css" media="print">

        <!-- Fonts -->
        <link rel="stylesheet" href="../../FontAwesome/css/font-awesome.css">
        <link rel="stylesheet" href="../../fonts/fonts.css">

        <!-- Highlight.js Stylesheets -->
        <link rel="stylesheet" href="../../highlight.css">
        <link rel="stylesheet" href="../../tomorrow-night.css">
        <link rel="stylesheet" href="../../ayu-highlight.css">

        <!-- Custom theme stylesheets -->

    </head>
    <body>
        <!-- Provide site root to javascript -->
        <script type="text/javascript">
            var path_to_root = "../../";
            var default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? "navy" : "light";
        </script>

        <!-- Work around some values being stored in localStorage wrapped in quotes -->
        <script type="text/javascript">
            try {
                var theme = localStorage.getItem('mdbook-theme');
                var sidebar = localStorage.getItem('mdbook-sidebar');

                if (theme.startsWith('"') && theme.endsWith('"')) {
                    localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
                }

                if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
                    localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
                }
            } catch (e) { }
        </script>

        <!-- Set the theme before any content is loaded, prevents flash -->
        <script type="text/javascript">
            var theme;
            try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
            if (theme === null || theme === undefined) { theme = default_theme; }
            var html = document.querySelector('html');
            html.classList.remove('no-js')
            html.classList.remove('light')
            html.classList.add(theme);
            html.classList.add('js');
        </script>

        <!-- Hide / unhide sidebar before it is displayed -->
        <script type="text/javascript">
            var html = document.querySelector('html');
            var sidebar = 'hidden';
            if (document.body.clientWidth >= 1080) {
                try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
                sidebar = sidebar || 'visible';
            }
            html.classList.remove('sidebar-visible');
            html.classList.add("sidebar-" + sidebar);
        </script>

        <nav id="sidebar" class="sidebar" aria-label="Table of contents">
            <div class="sidebar-scrollbox">
                <ol class="chapter"><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">1.</strong> 类型系统</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../01_类型系统/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow.html"><strong aria-hidden="true">1.1.</strong> Rust Concept Clarification Deref vs AsRef vs Borrow vs Cow</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust_Concept_Clarification_Deref_vs_AsRef_vs_Borrow_vs_Cow/Deref_AsRef_Borrow_Cow释义.html"><strong aria-hidden="true">1.2.</strong> Deref AsRef Borrow Cow 释义</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然/Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然.html"><strong aria-hidden="true">1.3.</strong> Rust的Borrow和AsRef：让你的代码用起来像呼吸一样自然</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust的Cow类型有什么用？详解Cow及其用途/Rust的Cow类型有什么用？详解Cow及其用途.html"><strong aria-hidden="true">1.4.</strong> Rust的Cow类型有什么用？详解Cow及其用途</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/判别Fn、FnMut、FnOnce的标准/判别Fn、FnMut、FnOnce的标准.html"><strong aria-hidden="true">1.5.</strong> 判别Fn、FnMut、FnOnce的标准</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/一行代码告诉你内部可变性的真相(UnsafeCell)/一行代码告诉你内部可变性的真相(UnsafeCell).html"><strong aria-hidden="true">1.6.</strong> 一行代码告诉你内部可变性的真相(UnsafeCell)</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Tour_of_Rust's_Standard_Library_Traits/Tour_of_Rust's_Standard_Library_Traits.html"><strong aria-hidden="true">1.7.</strong> Tour of Rust's Standard Library Traits</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/逆变、协变与子类型，以及Rust/逆变、协变与子类型，以及Rust.html"><strong aria-hidden="true">1.8.</strong> 逆变、协变与子类型，以及Rust</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust自引用结构、Pin与Unpin/Rust自引用结构、Pin与Unpin.html"><strong aria-hidden="true">1.9.</strong> Rust自引用结构、Pin与Unpin</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/为什么Rust需要Pin,Unpin/为什么Rust需要Pin,Unpin.html"><strong aria-hidden="true">1.10.</strong> 译：为什么 Rust 需要 Pin, Unpin ？</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/定海神针Pin和Unpin/定海神针Pin和Unpin.html"><strong aria-hidden="true">1.11.</strong> 译：定海神针 Pin 和 Unpin</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/sizedness-in-rust/sizedness-in-rust.html"><strong aria-hidden="true">1.12.</strong> Sizedness in Rust</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/Rust生命周期集大成者PhantomData〈T〉/Rust生命周期集大成者PhantomData〈T〉.html"><strong aria-hidden="true">1.13.</strong> Rust生命周期集大成者 PhantomData&lt;T&gt;</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操_Part_0.html"><strong aria-hidden="true">1.14.</strong> 数据库表达式执行的黑魔法：用Rust做类型体操 Part 0</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：GAT实现引用类型关联_Part_1.html"><strong aria-hidden="true">1.15.</strong> 数据库表达式执行的黑魔法：GAT实现引用类型关联 Part 1</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用HRTB写bound_Part_2.html"><strong aria-hidden="true">1.16.</strong> 数据库表达式执行的黑魔法：用HRTB写bound Part 2</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：用Rust做类型体操之用宏展开重复代码_Part_3_&_4.html"><strong aria-hidden="true">1.17.</strong> 数据库表达式执行的黑魔法：用Rust做类型体操之用宏展开重复代码 Part 3 & 4</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：与Rust编译器斗智斗勇之表达式向量化_Part_5_&_6.html"><strong aria-hidden="true">1.18.</strong> 数据库表达式执行的黑魔法：与Rust编译器斗智斗勇之表达式向量化 Part 5 & 6</a></li><li class="chapter-item expanded "><a href="../../01_类型系统/数据库表达式执行的黑魔法：用Rust做类型体操/数据库表达式执行的黑魔法：在Rust中用宏关联逻辑类型和实际类型_Part_7.html"><strong aria-hidden="true">1.19.</strong> 数据库表达式执行的黑魔法：在Rust中用宏关联逻辑类型和实际类型 Part 7</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">2.</strong> 生命周期</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../02_生命周期/Rust中的生命周期——从StrSplit实例说开去/Rust中的生命周期——从StrSplit实例说开去.html"><strong aria-hidden="true">2.1.</strong> Rust中的生命周期——从StrSplit实例说开去</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/与ChatGPT深度对话来学Rust生命周期/与ChatGPT深度对话来学Rust生命周期.html"><strong aria-hidden="true">2.2.</strong> 与ChatGPT深度对话来学Rust生命周期</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——early_bound与late_bound（1）/进击的Rust生命周期——early_bound与late_bound（1）.html"><strong aria-hidden="true">2.3.</strong> 进击的Rust生命周期——early_bound与late_bound（1）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——early_bound与late_bound（2）/进击的Rust生命周期——early_bound与late_bound（2）.html"><strong aria-hidden="true">2.4.</strong> 进击的Rust生命周期——early_bound与late_bound（2）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——一力降十会的MIR（1）/进击的Rust生命周期——一力降十会的MIR（1）.html"><strong aria-hidden="true">2.5.</strong> 进击的Rust生命周期——一力降十会的MIR（1）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/进击的Rust生命周期——一力降十会的MIR（2）/进击的Rust生命周期——一力降十会的MIR（2）.html"><strong aria-hidden="true">2.6.</strong> 进击的Rust生命周期——一力降十会的MIR（2）</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/Common_Rust_Lifetime_Misconceptions/Common_Rust_Lifetime_Misconceptions.html"><strong aria-hidden="true">2.7.</strong> Common Rust Lifetime Misconceptions</a></li><li class="chapter-item expanded "><a href="../../02_生命周期/Rust生命周期常见误区/Rust生命周期常见误区.html"><strong aria-hidden="true">2.8.</strong> 译：Rust生命周期常见误区</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">3.</strong> 无畏并发</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../05_无畏并发/简单写个Rust无锁队列/简单写个Rust无锁队列.html"><strong aria-hidden="true">3.1.</strong> 简单写个Rust无锁队列</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——混合自旋锁/进击的Rust多线程——混合自旋锁.html"><strong aria-hidden="true">3.2.</strong> 进击的Rust多线程——混合自旋锁</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/An_unsafe_tour_of_Rust's_Send_and_Sync/An_unsafe_tour_of_Rust's_Send_and_Sync.html"><strong aria-hidden="true">3.3.</strong> An unsafe tour of Rust's Send and Sync</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——Send与Sync/进击的Rust多线程——Send与Sync.html"><strong aria-hidden="true">3.4.</strong> 进击的Rust多线程——Send与Sync</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/进击的Rust多线程——离经叛道的PhantomData/进击的Rust多线程——离经叛道的PhantomData.html"><strong aria-hidden="true">3.5.</strong> 进击的Rust多线程——离经叛道的PhantomData</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust_Async_Pin概念解析/Rust_Async_Pin概念解析.html"><strong aria-hidden="true">3.6.</strong> Rust Async: Pin概念解析</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust和C++的并发库对比/Rust和C++的并发库对比.html"><strong aria-hidden="true">3.7.</strong> 译：Rust 和 C++ 的并发库对比</a></li><li class="chapter-item expanded "><a href="../../05_无畏并发/Rust原子类型和内存排序/Rust原子类型和内存排序.html"><strong aria-hidden="true">3.8.</strong> Rust原子类型和内存排序</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">4.</strong> 网络编程</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../06_网络编程/从编解码层面理解WebSocket_手写一个WebSocket/从编解码层面理解WebSocket_手写一个WebSocket.html"><strong aria-hidden="true">4.1.</strong> 从编解码层面理解WebSocket 手写一 个WebSocket</a></li><li class="chapter-item expanded "><a href="../../06_网络编程/透过Rust探索系统的本原：网络篇/透过Rust探索系统的本原：网络篇.html"><strong aria-hidden="true">4.2.</strong> 透过Rust探索系统的本原：网络篇</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">5.</strong> 轮子系列</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../07_轮子系列/700行Rust写一个内存分配器/700行Rust写一个内存分配器.html" class="active"><strong aria-hidden="true">5.1.</strong> 700行Rust写一个内存分配器</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/Rust：网络库的实现思路/Rust：网络库的实现思路.html"><strong aria-hidden="true">5.2.</strong> Rust：网络库的实现思路</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/Rust异步运行时基础部件/Rust异步运行时基础部件.html"><strong aria-hidden="true">5.3.</strong> Rust异步运行时基础部件</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（1）.html"><strong aria-hidden="true">5.4.</strong> 使用Rust+epoll编写异步IO框架（1）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（2）.html"><strong aria-hidden="true">5.5.</strong> 使用Rust+epoll编写异步IO框架（2）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/使用Rust+epoll编写异步IO框架/使用Rust+epoll编写异步IO框架（3）.html"><strong aria-hidden="true">5.6.</strong> 使用Rust+epoll编写异步IO框架（3）</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day1.html"><strong aria-hidden="true">5.7.</strong> 用rust从零开发一套web框架：day1</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day2.html"><strong aria-hidden="true">5.8.</strong> 用rust从零开发一套web框架：day2</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day3.html"><strong aria-hidden="true">5.9.</strong> 用rust从零开发一套web框架：day3</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day4.html"><strong aria-hidden="true">5.10.</strong> 用rust从零开发一套web框架：day4</a></li><li class="chapter-item expanded "><a href="../../07_轮子系列/用rust从零开发一套web框架/用rust从零开发一套web框架：day5.html"><strong aria-hidden="true">5.11.</strong> 用rust从零开发一套web框架：day5</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">6.</strong> 奇技淫巧</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Copy-On-Write是不是优化？/Copy-On-Write是不是优化？.html"><strong aria-hidden="true">6.1.</strong> 译：Copy-On-Write是不是优化？</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/揭秘神奇的Rust_Axum风格的函数实现/揭秘神奇的Rust_Axum风格的函数实现.html"><strong aria-hidden="true">6.2.</strong> 译：揭秘神奇的 Rust Axum 风格的函数实现</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/“变长参数”函数与回调/“变长参数”函数与回调.html"><strong aria-hidden="true">6.3.</strong> “变长参数”函数与回调</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Rust字符串格式化的幕后：format_args!()/Rust字符串格式化的幕后：format_args!().html"><strong aria-hidden="true">6.4.</strong> 译：Rust字符串格式化的幕后：format_args!()</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/给Rust带来一点C++特产/给Rust带来一点C++特产.html"><strong aria-hidden="true">6.5.</strong> 给Rust带来一点C++特产</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/一步步实现_Rust_Bevy_ECS_的_System_简化版本/一步步实现_Rust_Bevy_ECS_的_System_简化版本.html"><strong aria-hidden="true">6.6.</strong> 一步步实现 Rust Bevy ECS 的 System 简化版本</a></li><li class="chapter-item expanded "><a href="../../08_奇技淫巧/Exploring_Design_Patterns_in_Rust_with_Algorithmic_Trading_Examples/Exploring_Design_Patterns_in_Rust_with_Algorithmic_Trading_Examples.html"><strong aria-hidden="true">6.7.</strong> Exploring Design Patterns in Rust with Algorithmic Trading Examples</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">7.</strong> 源码分析</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：bytes源码分析/Rust并发：bytes源码分析.html"><strong aria-hidden="true">7.1.</strong> Rust并发：bytes源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：标准库Arc源码分析/Rust并发：标准库Arc源码分析.html"><strong aria-hidden="true">7.2.</strong> Rust并发：标准库Arc源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust并发：标准库sync_Once源码分析/Rust并发：标准库sync_Once源码分析.html"><strong aria-hidden="true">7.3.</strong> Rust并发：标准库sync::Once源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust源码阅读：引用计数Rc/Rust源码阅读：引用计数Rc.html"><strong aria-hidden="true">7.4.</strong> Rust源码阅读：引用计数Rc</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust源码阅读：Cell、RefCell与内部可变性/Rust源码阅读：Cell、RefCell与内部可变性.html"><strong aria-hidden="true">7.5.</strong> Rust源码阅读： Cell、RefCell与内部可变性</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/关于_Rust_的_UnsafeCell、Cell_与_RefCell/关于_Rust_的_UnsafeCell、Cell_与_RefCell.html"><strong aria-hidden="true">7.6.</strong> 关于 Rust 的 UnsafeCell、Cell 与 RefCell</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust_Async_async-stream源码分析/Rust_Async_async-stream源码分析.html"><strong aria-hidden="true">7.7.</strong> Rust Async: async-stream源码分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/走进Tokio的异步世界/走进Tokio的异步世界.html"><strong aria-hidden="true">7.8.</strong> 走进 Tokio 的异步世界</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/tokio.rs_runtime的实现/tokio.rs_runtime的实现.html"><strong aria-hidden="true">7.9.</strong> tokio.rs runtime 的实现</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_internals/Tokio_internals.html"><strong aria-hidden="true">7.10.</strong> Tokio internals</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_internals/译文：Tokio內部机制.html"><strong aria-hidden="true">7.11.</strong> 译：Tokio 内部机制</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Rust_Axum_HTTP_框架的架构分析/Rust_Axum_HTTP_框架的架构分析.html"><strong aria-hidden="true">7.12.</strong> Rust Axum HTTP 框架的架构分析</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/安利一个Rust_Game_Engine：Bevy--ECS部分/安利一个Rust_Game_Engine：Bevy--ECS部分.html"><strong aria-hidden="true">7.13.</strong> 安利一个Rust Game Engine：Bevy--ECS部分</a></li><li class="chapter-item expanded "><a href="../../09_源码分析/Tokio_解析之任务调度/Tokio_解析之任务调度.html"><strong aria-hidden="true">7.14.</strong> Tokio 解析之任务调度</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">8.</strong> 生态观察</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../11_生态观察/Rust_web_frameworks_have_subpar_error_reporting/Rust_web_frameworks_have_subpar_error_reporting.html"><strong aria-hidden="true">8.1.</strong> Rust web frameworks have subpar error reporting</a></li><li class="chapter-item expanded "><a href="../../11_生态观察/SeaORM：要做Rust版本的ActiveRecord/SeaORM：要做Rust版本的ActiveRecord.html"><strong aria-hidden="true">8.2.</strong> SeaORM：要做Rust版本的ActiveRecord</a></li></ol></li><li class="chapter-item expanded "><a href="../../empty.html"><strong aria-hidden="true">9.</strong> 死灵终极</a></li><li><ol class="section"><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_总述.html"><strong aria-hidden="true">9.1.</strong> 译：Learn Rust the Dangerous Way 总述</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_0.html"><strong aria-hidden="true">9.2.</strong> 译：Learn Rust the Dangerous Way 0</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_1.html"><strong aria-hidden="true">9.3.</strong> 译：Learn Rust the Dangerous Way 1</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_2.html"><strong aria-hidden="true">9.4.</strong> 译：Learn Rust the Dangerous Way 2</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_3.html"><strong aria-hidden="true">9.5.</strong> 译：Learn Rust the Dangerous Way 3</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_4.html"><strong aria-hidden="true">9.6.</strong> 译：Learn Rust the Dangerous Way 4</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Learn_Rust_the_Dangerous_Way_系列文章翻译/Learn_Rust_the_Dangerous_Way_系列文章翻译_5.html"><strong aria-hidden="true">9.7.</strong> 译：Learn Rust the Dangerous Way 5</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（一）.html"><strong aria-hidden="true">9.8.</strong> Unsafe Rust 随堂小测（一）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（二）.html"><strong aria-hidden="true">9.9.</strong> Unsafe Rust 随堂小测（二）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测（三）.html"><strong aria-hidden="true">9.10.</strong> Unsafe Rust 随堂小测（三）</a></li><li class="chapter-item expanded "><a href="../../12_死灵终极/Unsafe_Rust_随堂小测/Unsafe_Rust_随堂小测参考答案.html"><strong aria-hidden="true">9.11.</strong> Unsafe Rust 随堂小测参考答案</a></li></ol></li></ol>
            </div>
            <div id="sidebar-resize-handle" class="sidebar-resize-handle"></div>
        </nav>

        <div id="page-wrapper" class="page-wrapper">

            <div class="page">
                                <div id="menu-bar-hover-placeholder"></div>
                <div id="menu-bar" class="menu-bar sticky bordered">
                    <div class="left-buttons">
                        <button id="sidebar-toggle" class="icon-button" type="button" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
                            <i class="fa fa-bars"></i>
                        </button>
                        <button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
                            <i class="fa fa-paint-brush"></i>
                        </button>
                        <ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
                            <li role="none"><button role="menuitem" class="theme" id="light">Light (default)</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
                            <li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
                        </ul>
                        <button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
                            <i class="fa fa-search"></i>
                        </button>
                    </div>

                    <h1 class="menu-title">Rust 优秀博文</h1>

                    <div class="right-buttons">
                        <a href="../../print.html" title="Print this book" aria-label="Print this book">
                            <i id="print-button" class="fa fa-print"></i>
                        </a>

                    </div>
                </div>

                <div id="search-wrapper" class="hidden">
                    <form id="searchbar-outer" class="searchbar-outer">
                        <input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
                    </form>
                    <div id="searchresults-outer" class="searchresults-outer hidden">
                        <div id="searchresults-header" class="searchresults-header"></div>
                        <ul id="searchresults">
                        </ul>
                    </div>
                </div>

                <!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
                <script type="text/javascript">
                    document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
                    document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
                    Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
                        link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
                    });
                </script>

                <div id="content" class="content">
                    <main>
                        <h1 id="700行rust写一个内存分配器"><a class="header" href="#700行rust写一个内存分配器">700行Rust写一个内存分配器</a></h1>
<p>作者：<a href="https://www.zhihu.com/people/cowsay">Cowsay</a></p>
<p>原载：<a href="https://zhuanlan.zhihu.com/p/637134392">https://zhuanlan.zhihu.com/p/637134392</a></p>
<p>最近听说了一些关于ARM架构的抱怨。弱内存模型带来的离谱性能表现，导致做一些简单内存管理时，开数组线性搜索由于更好的空间局部性可以把用链表常数时间搜索按在地上摩擦。</p>
<p>「即便如此」，我想，「系统提供的动态内存分配器还是通过链表管理内存的呀」。</p>
<p>如果能设计一种，内存分配区和元数据分开存放的方案，让内存分配器不需要大范围触碰被分配的内存，是否可以通过空间局部性的优势提升性能，尤其是对大量内存块的分配性能呢？</p>
<p>要回答这个问题，就要对两种方案分别实现一遍，公平公正地进行对比。正好<code>#[global_allocator]</code>已经稳定多时，不如借此机会来练习一下实现<code>GlobalAlloc</code>吧！</p>
<p>坏消息是，这篇文章只会写到一半（其实还不到一半）：一方面，这件事的工作量远远超过我的预想；另一方面，活突然来了，摸鱼的时光总是这么短暂（悲</p>
<p>在这篇文章中你会看到：</p>
<ul>
<li>如何用最偷懒的方式实现一个还算能用的<code>GlobalAlloc</code>（对于<code>Alloc</code>也适用，但是它还没稳定所以先不讨论）</li>
<li>当700行代码中包含181个<code>unsafe</code>的时候，用Rust还有什么意义</li>
<li>这个实现实际用起来体验怎么样，性能又怎么样（以及一些未来的跑分计划）</li>
</ul>
<p>代码归档在<a href="https://link.zhihu.com/?target=https%3A//github.com/whoiscc/simpile">whoiscc/simpile (github.com)</a>。</p>
<hr />
<p>说起简单的动态内存分配器实现，那么无论如何也不会错过的当然是</p>
<p><a href="https://gee.cs.oswego.edu/dl/html/malloc.html">https://gee.cs.oswego.edu/dl/html/malloc.html</a></p>
<p>没别的好说的，照着它从头写到尾就完事了。</p>
<p>对于Rust，唯一需要定制的一点是<code>GlobalAlloc</code>的接口对分配的内存有对齐的要求。换句话说我们实际上是要实现<code>memalign</code>。我懒得去看dlmalloc的实际实现，就自己土办法造了一个出来。</p>
<p>首先是设计内存格式。返回给用户的指针为，从默认返回的指针（即8字节元数据之后的地址）开始，第一个满足对齐要求的地址。 即在元数据和用户内存之间有一段padding。这会导致在释放内存时，不能直接从用户指针向前倒推8个字节找到元数据。因此，我拓展了元数据当中状态位的定义。目前使用了两个状态位的四种值：</p>
<ul>
<li><code>00</code>，这个元数据并不是一个块的起始，而是padding。元数据中记录的大小（即通常存放的块大小）实际为padding导致的用户数据和元数据之间的偏移量。</li>
<li><code>01</code>，这是一个分配给用户使用的块。</li>
<li><code>10</code>，这是一个空闲的块，且它的低地址邻居正在被分配。</li>
<li><code>11</code>，这个块和它的低地址邻居都在被分配。</li>
</ul>
<p>可以注意到<code>00</code>被用作了特殊含义，这是因为我们的实现保证永远不会有两个相邻的空闲块，即一旦有相邻空闲块就会立刻被合并，因此<code>00</code>的原始含义是不可能发生的。</p>
<p>然后是对算法的修正。在原本算法的基础上，<code>alloc</code>和<code>realloc</code>多了一种失败路径：字节数够用了，但是没对齐。比如说请求16字节对齐的1024字节内存，如果搜索到一个内存块刚好有1024字节的用户内存，但是起始地址只是8字节对齐的，那么它就不能被用来分配。在<code>alloc</code>中我们必须继续寻找更大的内存块，而在<code>realloc</code>中我们只能放弃就地扩容。</p>
<p>不过好消息是，因为dlmalloc保证了至少8字节对齐，而一般的对齐要求也不会超过8字节（除了涉及向量指令的特殊数据结构），所以这些因为对齐而损失的时间和空间并不显著，可以不作特殊优化。</p>
<hr />
<p>在实现数据块的时候，我利用了条件编译，在开发（dev）构建时在结构体中包含一些调试信息</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
struct Chunk {
    data: NonNull&lt;u8&gt;,
    #[cfg(any(dev, test))]
    limit: NonNull&lt;u8&gt;,
    #[cfg(not(any(dev, test)))]
    limit: (),
}
<span class="boring">}
</span></code></pre></pre>
<p>从而可以在寻找高地址邻居的时候可以检查是否（因为bug）越过了堆的高地址边界。</p>
<p>在发布构建时，<code>limit</code>会被丢弃，从而niche优化又可以确保<code>Option&lt;Chunk&gt;</code> 只占用8字节的内存。对应的，要在源文件开头加上一句</p>
<pre><code class="language-text">#![cfg_attr(not(any(dev, test)), allow(clippy::unit_arg, clippy::unit_cmp))]
</code></pre>
<hr />
<p>虽然Rust没有任何要求我去这么做，但是我还是把分配和释放内存的函数实现为了<code>&amp;mut self</code>方法，因为它们确实并不可重入。而<code>GlobalAlloc</code>显然要求我们提供并发安全的<code>&amp;self</code>方法。</p>
<p>我并不打算在这里花费精力，也没打算像一个现代的内存分配器一样为多线程性能进行精妙的设计，所以只是简单地用<code>Mutex</code>把堆包了起来，并且把它当自旋锁用，调用它的非阻塞接口进行忙等，因为显然不会有死锁发生（但愿也没有优先级倒置，因为内存分配的过程也是一个计算密集过程）。这样的性能肯定不怎么样（接下来就会看到），但是能用。</p>
<p>堆由我们的分配器进行管理，但它所拥有的内存最终还是得从操作系统中得到。我把获取连续内存条的行为抽象成了一个</p>
<pre><pre class="playground"><code class="language-rust"><span class="boring">#![allow(unused)]
</span><span class="boring">fn main() {
</span>pub trait Space
where
    Self: DerefMut&lt;Target = [u8]&gt;,
{
    fn set_size(&amp;mut self, bytes: usize) -&gt; bool;

    fn grow(&amp;mut self, min_bytes: usize) -&gt; bool {
        self.set_size(self.len() * usize::max((min_bytes / self.len() + 1).next_power_of_two(), 1))
    }
}
<span class="boring">}
</span></code></pre></pre>
<p>并且写了两个实现。一个实现通过<code>mmap</code>/<code>mremap</code>系统调用获得内存（虽然正统的方法应该是用<code>sbrk</code>，但是又能有什么区别嘛）。另外一个通过一个固定长度的<code>Box&lt;[u8]&gt;</code>提供内存，并且不支持扩容，专门用于单元测试。</p>
<p>最后，我们的分配器需要作为只读的静态变量，而初始化堆的元数据又必须进行且只进行一次。恰好刚刚稳定的<code>OnceLock</code>符合我们的需求。因此，完整的hello world示例如下</p>
<pre><pre class="playground"><code class="language-rust">use std::{alloc::GlobalAlloc, sync::OnceLock};

use simpile::{linked::Allocator, space::Mmap, Space};

struct Global(OnceLock&lt;Allocator&lt;Mmap&gt;&gt;);

impl Global {
    fn init() -&gt; Allocator&lt;Mmap&gt; {
        let mut space = Mmap::new();
        space.set_size(128 &lt;&lt; 10); // 128 KB
        Allocator::new(space)
    }
}

unsafe impl GlobalAlloc for Global {
    unsafe fn alloc(&amp;self, layout: std::alloc::Layout) -&gt; *mut u8 {
        self.0.get_or_init(Self::init).alloc(layout)
    }

    unsafe fn dealloc(&amp;self, ptr: *mut u8, layout: std::alloc::Layout) {
        self.0.get_or_init(Self::init).dealloc(ptr, layout)
    }

    unsafe fn realloc(&amp;self, ptr: *mut u8, layout: std::alloc::Layout, new_size: usize) -&gt; *mut u8 {
        self.0
            .get_or_init(Self::init)
            .realloc(ptr, layout, new_size)
    }

    unsafe fn alloc_zeroed(&amp;self, layout: std::alloc::Layout) -&gt; *mut u8 {
        self.0.get_or_init(Self::init).alloc_zeroed(layout)
    }
}

#[global_allocator]
static GLOBAL: Global = Global(OnceLock::new());

fn main() {
    GLOBAL.0.get_or_init(|| unreachable!()).sanity_check();
    println!(&quot;Hello, world!&quot;);
}
</code></pre></pre>
<p>还是一样，效果肯定不怎么样，但是能用。根据GLIBC的文档，堆增长默认是以128KB为单位，因此这应该是对于原生内存分配器的最佳近似了。</p>
<hr />
<p>我还简单写了几个微性能测试（microbenchmark)。由于懒惰这里直接贴criterion绘制的结果。横坐标会测量值（用时），越靠左越好。</p>
<p>第一个是进行单次分配/释放循环的用时</p>
<p><img src="pict/001.png" alt="" /></p>
<p>可以看到系统实现大概以14倍性能吊打我们的实现。这还玩个毛线啊（摔</p>
<p>当然，我们多少还是能为此找到一些借口：</p>
<ul>
<li>如上面提到的，我们的实现用<code>OnceLock&lt;Mutex&lt;_&gt;&gt;</code>的方式投机取巧地满足了并发安全的要求，但是也因此在单线程工作是付出了不必要的性能开销。实际上，单纯操作几次原子变量的延迟就已经非常可观了。
虽然没有仔细考察过，但是系统实现大概会为单线程应用开辟专门的fast path，规避掉所有的同步动作。因此，只要我们也如此般做就可以弥补这个差距。而这显然是可行的。</li>
<li>虽然dlmalloc对于缓存的描述含糊其辞，但是对于这种重复的相同请求，dlmalloc，以及基于它拓展得到的GLIBC分配器，几乎一定会缓存刚刚回收的内存块，并且在下一次分配时直接复用。相比之下我们的实现不会命中任何捷径，相反还要走一条相对缓慢的路径（和一个很大的高地址邻居进行合并），进一步拉大了差距。</li>
</ul>
<p>下一个测试是循环分配100个内存块，分别为1字节到100字节，然后依次释放</p>
<p><img src="pict/002.png" alt="" /></p>
<p>这回的性能差距不到5倍，比刚才就好多了。另外，系统实现的用时（超过2微秒）要大于上一个测试用时（约8纳秒）的100倍。这都说明我们上面的解释是有道理的。</p>
<p>最后我还测了一下把释放顺序翻转为后进先出</p>
<p><img src="pict/003.png" alt="" /></p>
<p>系统实现的性能保持不变，而我们的实现性能略有下降，原因有待分析。</p>
<hr />
<p>下一步怎么测？（本来是这篇文章的一部分，来不及做了呜呜呜）</p>
<p>dlmalloc的页面上列举了一些高强度依赖动态内存分配的应用</p>
<blockquote>
<p>... real loads that depend heavily on dynamic allocation -- windowing toolkits, GUI applications, compilers, interpretors, development tools, network (packet)-intensive programs, graphics-intensive packages, web browsers, string-processing applications, and so on.</p>
</blockquote>
<p>这当中最吸引我眼球的当然是「compilers」。要问为什么，那当然是因为有一个现成的</p>
<p><a href="https://link.zhihu.com/?target=https%3A//github.com/rust-lang/rustc-perf">rust-lang/rustc-perf: Website for graphing performance of rustc (github.com)github.com/rust-lang/rustc-perf</a></p>
<p>因此，只要能成功地用我们的实现把rustc跑起来，我们就免费得到了一大堆端到端的测试结果，甚至还有一个配套的可视化网站。</p>
<p>真好。要是我有时间把它搞了就更好了。呜呜呜。</p>
<hr />
<p>最后来讨论一下<code>unsafe</code>。</p>
<p>正如开头提到的。这个仓库的Rust代码已经完全是<code>unsafe</code>的形状了（。这一方面是因为我们实现的就是一个内存分配器，自然不可能内存安全；另一方面也是因为我非要犯强迫症打开<code>#![warn(unsafe_op_in_unsafe_fn)]</code>，虽然在这次的代码里确实没什么大用。</p>
<p>我常常看到一种论述，说从C++转Rust，然后代码写得到处都是<code>unsafe</code>，一点都不安全还给自己找罪受，非常不划算所以不推荐Rust云云。</p>
<p>对于写了<code>unsafe</code>会变得很不安全，我是完全认同的。这次的高强度<code>unsafe</code>编程实打实地让我见识了在内存不安全的模型下会出现的bug有多么的妖魔鬼怪。唉，Rust用多了还会磨灭我对bug的想象力，这是我没想到的。</p>
<p>但是，哪怕是去掉了内存安全的Rust，仍然保持了一定的优越性。</p>
<p>代码的简洁性和表达力仍然有所保证。虽然只实现了dlmalloc的一小部分，和原版的完整代码比行数并不公平，但是换作其他语言来写同样的逻辑，还是很难比Rust写得更短；如果更短，那么可读性一定会更差。</p>
<p>对于比较底层的指针操作部分，因为Rust的原生类型上有方法，因此可以写更加优雅和显式的链式调用，比如<code>.cast</code>而不是<code>reintrepret_cast</code>。另外，得益于对newtype范式的支持和推崇，我们可以非常自然地创建一个newtype，给指向块起始地址的指针一个全新的含义。这在C++中当然也是能做的（毕竟C++能做任何事情），但是没有任何的语言特性去引导这样的设计，不会为这样的设计提供任何正向反馈。最终，很多人可能还是选择用裸露在外的指针一路写到底。</p>
<p>而写到比较高层的操作部分，Rust丰富的语言和标准库特性就能派上用场了。在这篇代码中用到的特性基本都围绕着<code>Option&lt;NonNull&lt;u8&gt;&gt;</code>转，用它替代可能为null的原生指针，可以大幅度提升心智模型的安全性的同时，充分利用到Rust的<code>if let</code>等一系列基础设施。</p>
<p>除此之外，还有比如前面提到的基于构建profile的条件编译，也为「零开销sanity check」提供了很多的便利。当然还有<code>unsafe</code>本身。虽然这个密度的<code>unsafe</code>已经不能起到标记debug怀疑目标的作用了，但是还是会在很多时候引起人去反思代码的正确性，而这依然是很有意义的。最后，<code>GlobalAlloc</code>的接口定义也很棒：它定义的方法都是不安全的，从而把一部分责任留给了调用方。相比起之前用C去实现的时候，要去处理一些奇奇怪怪的比如用null指针调用<code>free</code>和<code>realloc</code>的情况，实现<code>GlobalAlloc</code>可以完全不用考虑这些，引起舒适。</p>
<p>我们还可以进一步期待着unsafe Rust的下一次进化。等到strict provenance稳定以后，更加严格的unsafe代码将会允许更多的工具为开发unsafe提供帮助。Rust的unsafe和其他语言之间区别将会更加明显。</p>
<p>最后，单元测试覆盖率工具也是绝赞好用呢</p>
<p><img src="pict/004.png" alt="" /></p>
<h1 id="700行rust写一个内存分配器---续"><a class="header" href="#700行rust写一个内存分配器---续">700行Rust写一个内存分配器 - 续</a></h1>
<p>接上文</p>
<p><a href="https://zhuanlan.zhihu.com/p/637134392">Cowsay：700行Rust写一个内存分配器135 赞同 · 6 评论文章</a></p>
<p>没想到来看的同学还挺多的，受宠若惊。在两个ddl之间的夹缝里又更新了一些好玩的内容。按照目前的进度剩下的内容大概一篇文章就能写完，所以到时候来个终篇，不搞序号了。</p>
<h3 id="no_std特性和条件编译"><a class="header" href="#no_std特性和条件编译">no_std，特性和条件编译</a></h3>
<p>上篇有同学建议支持no_std，我觉得很有道理。正好借此机会调整了整个特性/条件编译的架构。目前的设计是</p>
<ul>
<li><code>nix</code>特性：可选依赖，打开可以为<code>Mmap</code>结构体添加借助了系统调用的<code>Space</code> 实现</li>
<li><code>std</code>特性：依赖<code>nix</code>并额外启用若干依赖于<code>std</code>标准库的代码， 包括模糊测试的辅助逻辑（下面详细介绍）</li>
<li><code>paranoid</code>特性：启用实现中额外的查错字段和检查逻辑</li>
<li><code>switchable</code>特性：依赖<code>std</code>，添加一个可以在运行时动态切换<code>GlobalAlloc</code>实现的包裹实现</li>
</ul>
<p>如此一来，示例和性能测试因为用到<code>mmap</code>所以需要启用<code>std</code>特性，比如<code>cargo bench --features std</code>。而模糊测试则还要额外启动<code>paranoid</code>以打开全部的检查尽早发现bug。</p>
<p>注意到这些检查在<code>test</code>编译预设下都是启用的（即<code>#[cfg(any(test, feature = &quot;paranoid&quot;))]</code>）。这里额外添加一个特性是因为当我们的分配器代码库作为依赖被编译时，不会使用任何一种预设，所以只能通过特性。</p>
<p>于是，现在我们有了700行no_std模式的代码实现的内存分配器。原来的代码逻辑基本没有受到影响，主要是将内部数据结构的<code>Debug</code>实现重构成了不需要动态内存分配的做法，以及将<code>std::sync::Mutex</code>换成了<code>spin_lock::Mutex</code>，顺便还提升了一点性能。</p>
<h3 id="更多基准性能测试"><a class="header" href="#更多基准性能测试">更多基准性能测试</a></h3>
<p>在之前的基准测试之外，我又添加了几个测试项目。首先上次说到分配+释放单块内存的性能差距巨大，所以又加入一个相对较快的测试方式：提前将用于性能测试的内存块的高地址块分配掉，以确保释放内存时不会触发合并空块。其他的比较对象应该不会有性能上的区别，而我们的实现则会更快一点。</p>
<p>此外还有两个针对<code>realloc</code>的性能测试，分别为就地扩容和需要复制的场景。注意这些测试实际上除了<code>realloc</code>还包含了一些普通的分配/释放以触发对应的场景，所以它的结果一定程度上和对分配/释放的测试结果耦合。</p>
<p>最后，我还引入了两个比较对象：一个基于简单链表的精简实现<code>linked_list_allocator</code>，和<code>dlmalloc</code>，由社区大佬完成的对dlmalloc的porting，目的是为wasm平台提供一个可用的内存分配器。它们同样都是支持no_std的实现，比较起来应该算是公平。</p>
<p>那么测试的结果呢？我并不是很想放出来，因为我们的实现在每一项都是垫底的成绩┭┮﹏┭┮稍微令人好受一点的是，像之前的那种超过十倍的落后确实是没有了。多数测试都在2-3倍的性能差距范围，作为一个教学/练手用实现还算说得过去。</p>
<p>嘛，比<code>System</code>慢合情合理，比社区大佬的精妙代码慢也就算了，怎么会比链表慢……</p>
<h3 id="模糊测试"><a class="header" href="#模糊测试">模糊测试</a></h3>
<p>要说模糊测试（fuzzing）的目标，天底下可能找不到比内存分配器更理想的了。</p>
<p>这次尝试了使用afl。找到的相关项目有两个：<a href="https://link.zhihu.com/?target=https%3A//github.com/rust-fuzz/afl.rs">rust-fuzz/afl.rs</a>看起来相对易用，但是文档比较简略；<a href="https://link.zhihu.com/?target=https%3A//github.com/AFLplusplus/LibAFL">AFLplusplus/LibAFL</a>文档丰富而且似乎更加“官方”，但是想把测试搭建起来相对要费点功夫。最终我选择了前一个。</p>
<p>经过对若干bug的修复（疲惫），现在这个代码库应该属于比较安全了，下面是跑了3个小时的模糊测试的截图</p>
<p><img src="pict/005.png" alt="" /></p>
<p>虽然还有很多选项以及并行模糊可以上手尝试，但是作为一个兴趣项目这样应该就不错了吧。此外，我还顺手对<code>System</code>也模糊测试了一下，果不其然什么都没测出来。</p>
<h3 id="端到端性能测试"><a class="header" href="#端到端性能测试">端到端性能测试</a></h3>
<p>上篇提到了接下来准备用rustc配合rustc-perf来进行端到端的性能测试。我已经把它跑了起来，但是在切换到我们的内存分配器时遇到了点问题。</p>
<p>根据<code>compiler/rustc</code>包当中的注释，我们可以了解到因为一些复杂的原因，<code>#[global_allocator]</code>不能用，只能通过更底层的直接覆盖<code>malloc</code>/<code>free</code>/<code>realloc</code>/……等符号的方式来做。覆盖这些符号的一个后果就是它们和我们实现的<code>GlobalAlloc</code>接口对不上。一方面，像是<code>realloc</code>和<code>dealloc</code>中能拿到的<code>Layout</code>信息在这些接口中都没有提供；另一方面，不安全方法的契约，比如调用方保证不会给<code>realloc</code>传非法指针等等，这些接口的调用方也不会遵守。</p>
<p>总之，想把端到端跑起来看来还得再调一调。有空继续吧。</p>
<h3 id="空间局部性更好的新分配器"><a class="header" href="#空间局部性更好的新分配器">空间局部性更好的新分配器</a></h3>
<p>还记得我在上篇的一开头写的故事吗？</p>
<p>内存分配器的内存访问模式并没有好的空间局部性，为了搞清楚更好的空间局部性会带来多大的性能影响，我才写了所有这些。</p>
<p>那么，怎样的设计才能带来更好的空间局部性呢？</p>
<p>一个简单的想法是把元数据抽取出来，从夹杂在分配内存块之间变成连续排布在一个专门的区域内。当然，就算如此，分配的内存块依然不能简单地首尾相接，因为还要有后向指针，在释放内存块时用来找到对应的元数据。</p>
<p>哪怕只是这样，也可以说多少可能会有点好处的。因为单次分配的最小单位从24字节（实际占用32字节）减少到8字节（实际占用16字节），分配给用户的内存更加紧凑了，当应用请求了很多小块内存时，有机会节省CPU缓存的使用量。</p>
<p>当然，这样还是不够的，我还要继续寻找更极致的设计方案。最好就是能做到分配的内存块真的收尾相接，在分配过程中不需要对分配的内存地址（以及附近）进行任何访问。这样不管怎么样，这种方案都可能会在类似于disaggreated system/far memory一类的场合中起到神奇的效果。</p>
<p>希望早点有空继续吧。</p>
<p>编辑于 2023-07-03 14:58・IP 属地新加坡</p>

                    </main>

                    <nav class="nav-wrapper" aria-label="Page navigation">
                        <!-- Mobile navigation buttons -->
                            <a rel="prev" href="../../empty.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                                <i class="fa fa-angle-left"></i>
                            </a>

                            <a rel="next" href="../../07_轮子系列/Rust：网络库的实现思路/Rust：网络库的实现思路.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                                <i class="fa fa-angle-right"></i>
                            </a>

                        <div style="clear: both"></div>
                    </nav>
                </div>
            </div>

            <nav class="nav-wide-wrapper" aria-label="Page navigation">
                    <a rel="prev" href="../../empty.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
                        <i class="fa fa-angle-left"></i>
                    </a>

                    <a rel="next" href="../../07_轮子系列/Rust：网络库的实现思路/Rust：网络库的实现思路.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
                        <i class="fa fa-angle-right"></i>
                    </a>
            </nav>

        </div>




        <script type="text/javascript">
            window.playground_copyable = true;
        </script>


        <script src="../../elasticlunr.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../mark.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../searcher.js" type="text/javascript" charset="utf-8"></script>

        <script src="../../clipboard.min.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../highlight.js" type="text/javascript" charset="utf-8"></script>
        <script src="../../book.js" type="text/javascript" charset="utf-8"></script>

        <!-- Custom JS scripts -->


    </body>
</html>
